//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// hash_table_bucket_page.cpp
//
// Identification: src/storage/page/hash_table_bucket_page.cpp
//
// Copyright (c) 2015-2021, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "storage/page/hash_table_bucket_page.h"
#include "common/logger.h"
#include "common/util/hash_util.h"
#include "storage/index/generic_key.h"
#include "storage/index/hash_comparator.h"
#include "storage/table/tmp_tuple.h"

namespace bustub {

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::GetValue(KeyType key, KeyComparator cmp, std::vector<ValueType> *result) -> bool {
  for (uint32_t i = 0; i < elem_limit_; i++) {
    uint32_t idx = i / 8, off = i % 8;
    if (occupied_[idx] & (1 << off) && readable_[idx] & (1 << off)) {
      if (cmp(key, array_[i].first) == 0) {
        result->push_back(array_[i].second);
      }
    }
  }
  return !result->empty();
}

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::Insert(KeyType key, ValueType value, KeyComparator cmp) -> bool {
  bool res = GetValue(key, cmp, {});
  if (res) {
    // The key is already exists in the hash page
    for (uint32_t i = 0; i < elem_limit_; i++) {
      uint32_t idx = i / 8, off = i % 8;
      if (occupied_[idx] & (1 << off) && readable_[idx] & (1 << off)) {
        if (cmp(key, array_[i].first) == 0) {
          array_[i].second = value;
          return true;
        }
      }
    }
    // Some error occurs
    // panic("Error occur, the code should not arrived there!!")
  } else {
    // Now there is no key exists, just insert k,v into available place
    for (uint32_t i = 0; i < elem_limit_; i++) {
      uint32_t idx = i / 8, off = i % 8;
      if (!(occupied_[idx] & (1 << off))) {
        array_[i] = {key, value};
        occupied_[idx] |= (1 << off);
        readable_[idx] |= (1 << off);
        return true;
      }
    }
  }
  // No available place, return false
  return false;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::Remove(KeyType key, ValueType value, KeyComparator cmp) -> bool {
  if (GetValue(key, cmp, {})) {
    for (uint32_t i = 0; i < elem_limit_; i++) {
      uint32_t idx = i / 8, off = i % 8;
      if (occupied_[idx] & (1 << off) && readable_[idx] & (1 << off)) {
        if (cmp(key, array_[i].first) == 0) {
          occupied_[idx] ^= (1 << off);
          readable_[idx] ^= (1 << off);
        }
      }
    }
  }
  // No elems to remove
  return false;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::KeyAt(uint32_t bucket_idx) const -> KeyType {
  return array_[bucket_idx].first;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::ValueAt(uint32_t bucket_idx) const -> ValueType {
  return array_[bucket_idx].second;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
void HASH_TABLE_BUCKET_TYPE::RemoveAt(uint32_t bucket_idx) {
  uint32_t idx = bucket_idx / 8, off = bucket_idx % 8;
  occupied_[idx] ^= (1 << off);
  readable_[idx] ^= (1 << off);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::IsOccupied(uint32_t bucket_idx) const -> bool {
  uint32_t idx = bucket_idx / 8, off = bucket_idx % 8;
  return occupied_[idx] & (1 << off);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
void HASH_TABLE_BUCKET_TYPE::SetOccupied(uint32_t bucket_idx) {
  uint32_t idx = bucket_idx / 8, off = bucket_idx % 8;
  occupied_[idx] ^= (1 << off);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::IsReadable(uint32_t bucket_idx) const -> bool {
  uint32_t idx = bucket_idx / 8, off = bucket_idx % 8;
  return readable_[idx] & (1 << off);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
void HASH_TABLE_BUCKET_TYPE::SetReadable(uint32_t bucket_idx) {
  uint32_t idx = bucket_idx / 8, off = bucket_idx % 8;
  readable_[idx] ^= (1 << off);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::IsFull() -> bool {
  for (uint32_t i = 0; i < elem_limit_; i++) {
    uint32_t idx = i / 8, off = i % 8;
    if (!(occupied_[idx] & (1 << off))) {
      return false;
    }
  }
  return true;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::NumReadable() -> uint32_t {
  uint32_t sum = 0;
  for (uint32_t i = 0; i < elem_limit_; i++) {
    uint32_t idx = i / 8, off = i % 8;
    if (readable_[idx] & (1 << off)) {
      sum++;
    }
  }
  return sum;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::IsEmpty() -> bool {
  for (uint32_t i = 0; i < elem_limit_; i++) {
    uint32_t idx = i / 8, off = i % 8;
    if (occupied_[idx] & (1 << off)) {
      return false;
    }
  }
  return true;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
void HASH_TABLE_BUCKET_TYPE::PrintBucket() {
  uint32_t size = 0;
  uint32_t taken = 0;
  uint32_t free = 0;
  for (size_t bucket_idx = 0; bucket_idx < BUCKET_ARRAY_SIZE; bucket_idx++) {
    if (!IsOccupied(bucket_idx)) {
      break;
    }

    size++;

    if (IsReadable(bucket_idx)) {
      taken++;
    } else {
      free++;
    }
  }

  LOG_INFO("Bucket Capacity: %lu, Size: %u, Taken: %u, Free: %u", BUCKET_ARRAY_SIZE, size, taken, free);
}

// DO NOT REMOVE ANYTHING BELOW THIS LINE
template class HashTableBucketPage<int, int, IntComparator>;

template class HashTableBucketPage<GenericKey<4>, RID, GenericComparator<4>>;
template class HashTableBucketPage<GenericKey<8>, RID, GenericComparator<8>>;
template class HashTableBucketPage<GenericKey<16>, RID, GenericComparator<16>>;
template class HashTableBucketPage<GenericKey<32>, RID, GenericComparator<32>>;
template class HashTableBucketPage<GenericKey<64>, RID, GenericComparator<64>>;

// template class HashTableBucketPage<hash_t, TmpTuple, HashComparator>;

}  // namespace bustub
